package com.mango.leet.code.week1.game288;

/**
 * 6038. 向表达式添加括号后的最小结果
 */
/**
 * 给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2> 表示正整数。
 *
 * 请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到 最小 可能值。左括号 必须 添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。
 *
 * 返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到 最小 可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。
 *
 * 生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。
 *
 *
 *
 * 示例 1：
 *
 * 输入：expression = "247+38"
 * 输出："2(47+38)"
 * 解释：表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。
 * 注意 "2(4)7+38" 不是有效的结果，因为右括号必须添加在 '+' 的右侧。
 * 可以证明 170 是最小可能值。
 * 示例 2：
 *
 * 输入：expression = "12+34"
 * 输出："1(2+3)4"
 * 解释：表达式计算得到 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20 。
 * 示例 3：
 *
 * 输入：expression = "999+999"
 * 输出："(999+999)"
 * 解释：表达式计算得到 999 + 999 = 1998 。
 *
 *
 * 提示：
 *
 * 3 <= expression.length <= 10
 * expression 仅由数字 '1' 到 '9' 和 '+' 组成
 * expression 由数字开始和结束
 * expression 恰好仅含有一个 '+'.
 * expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围
 */

/**
 * @Author: mango
 * @Date: 2022/4/10 11:15 上午
 */
public class LC6038 {
    public static void main(String[] args) {
        System.out.println(new Solution().minimizeResult("12+34"));
        System.out.println(new Solution().minimizeResult("247+38"));
    }
    static class Solution {
        // 双指针
        public String minimizeResult(String expression) {
            int plusIndex = expression.indexOf("+");
            int n = expression.length();
            int result = Integer.MAX_VALUE;
            String resultStr = "";
            for(int i=plusIndex-1;i>=0;i--){
                for(int j=plusIndex+1;j<n;j++){
                    String resultTemp = "";
                    int left = 1;
                    if(i!=0) {
                        left = Integer.valueOf(expression.substring(0, i));
                    }
                    int mid1 = Integer.valueOf(expression.substring(i,plusIndex));
                    int mid2 = Integer.valueOf(expression.substring(plusIndex+1,j+1));
                    int right = 1;
                    if(j!=n-1){
                        right = Integer.valueOf(expression.substring(j+1));
                    }
                    int temp = left * (mid1 + mid2) * right;
                    if(i!=0){
                        resultTemp += left;
                    }
                    resultTemp += "("+mid1+"+"+mid2+")";
                    if(j!=n-1){
                        resultTemp += right;
                    }
                    System.out.println(left+"("+mid1+"+"+mid2+")"+right+"="+temp);
                    if(temp<result){
                        result = temp;
                        resultStr = resultTemp;
                    }
                }
            }
            return resultStr;
        }
    }
}
